package 简单算法;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-24
 * @Description: 给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
 * 样例
 * 样例 1:
 * 输入:  [[1,3,1],[1,5,1],[4,2,1]]
 * 输出: 7
 * 样例解释：
 * 路线为： 1 -> 3 -> 1 -> 1 -> 1。
 * 样例 2:
 * 输入:  [[1,3,2]]
 * 输出:  6
 * 解释:
 * 路线是： 1 -> 3 -> 2
 * 注意事项
 * 你在同一时间只能向下或者向右移动一步
 **/
public class 最小路径和 {
    public static void main(String[] args) {
        最小路径和 s = new 最小路径和();
        System.out.println(s.minPathSum(new int[][]{{1, 2, 5}, {3, 5, 1}, {4, 2, 2}}));
    }

    public int minPathSum(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int M = grid.length;
        int N = grid[0].length;
        int[][] sum = new int[M][N];

        sum[0][0] = grid[0][0];
        //1 2 5
        //3 5 1
        //4 2 2

        //计算纵列
        for (int i = 1; i < M; i++) {
            sum[i][0] = sum[i - 1][0] + grid[i][0];
        }

        //计算横列
        for (int i = 1; i < N; i++) {
            sum[0][i] = sum[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < M; i++) {
            for (int j = 1; j < N; j++) {
                sum[i][j] = Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
            }
        }

        return sum[M - 1][N - 1];
    }
}
